/**
*  \file list.h
*
*  \brief Double Linked List.
*
*  \author   Michael J. Hohmann  <michael.hohmann@linde-mh.de>
*
*  This header file provide a collection of macros to maintain linked lists.
*
*  A list consist of a head object and a an arbitrarily number of linked node objects.
*  Each head has internaly linked two node objects as header and trailer of the linked list.
*  An empty (and initialized) head looks like this.
*
*  \code
*             Header      Trailer
*  NULL<------[prev]<-----[prev]
*             [next]----->[next]----->NULL
*  \endcode
*
*  A linked list with two elements looks like this.
*  \code
*              Header      1st         2nd         Trailer
*  NULL<------[prev]<-----[prev]<-----[prev]<-----[prev]
*             [next]----->[next]----->[next]----->[next]----->NULL
*  \endcode
*
*  Common use:
*  \code
*  LIST_NODE_STRUCT(node,int);
*  LIST_HEAD_STRUCT(head,struct node);
*
*  struct node a,b,c;
*  struct head my_head;
*
*  LIST_INITIALIZE(&my_head);
*
*  LIST_DATA(&a)=1;
*  LIST_DATA(&b)=2;
*  LIST_DATA(&c)=3;
*
*  LIST_PUSH_FRONT( &my_head, &a );
*  LIST_PUSH_BACK(  &my_head, &b );
*  LIST_PUSH_BACK(  &my_head, &c );
*
*  LIST_FOR_EACH(&my_head, p)
*  {
*    print("%i\n",*LIST_DATA(&p) );
*  }
*  \endcode
*
*/

#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED

/*================================================[ public includes  ]================================================*/

/*================================================[ public defines   ]================================================*/

/** Struct definition of list node.
*
*  The macro LIST_NODE_STRUCT() define a struct with the ability of being linked in a double
*  linked list and provide the passed datatype as user data.
*
*  \param name         Name for the new type.
*
*  \param type         Type specifier of userdata.
*
*  \see LIST_HEAD_STRUCT()
*
*  \hideinitializer
*/
#define LIST_NODE_STRUCT(name,type) \
struct name                         \
{                                   \
   struct name *prev;               \
   struct name *next;               \
   type data;                       \
}

/** Stuct definition of list head.
*
*  LIST_HEAD_TYPEDEF() will create a list-head for passed type.
*  The type of list nodes have to be declared as LIST_NODE_STRUCT() before.
*
*  \param name         Name of the created struct.
*
*  \param type         Type of user data.
*
*  \see LIST_NODE_STRUCT()
*
*  \hideinitializer
*/
#define LIST_HEAD_STRUCT(name,type) \
struct name                         \
{                                   \
   struct                           \
   {                                \
      type *prev;                   \
      type *next;                   \
   } header, trailer;               \
}

/** Initialization of list handle.
*
*  LIST_INIT() will initialize the passed list-head object.
*  A call of LIST_INIT() is neccessary before the use of any other macro.
*
*  \param list          Handle to a list object.
*
*  \hideinitializer
*/
#define LIST_INIT( list )                                \
do{                                                      \
   (list)->header.next   = (void*)&(list)->trailer;      \
   (list)->header.prev   = (void*) 0;                    \
   (list)->trailer.next  = (void*) 0;                    \
   (list)->trailer.prev  = (void*)&(list)->header;       \
}while(0)

/** Get pointer to user data
*
*  LIST_DATA() will return a pointer to the user data of a list element.
*
*  \param node         Handle to an list element.
*
*  \return             Pointer to the user data object of the list element.
*
*  \hideinitializer
*/
#define LIST_DATA( node )     ( & ((node)->data) )

/** Get next list element.
*
*  LIST_NEXT() will return a pointer to the next element associated to the lis.
*
*  \param node         Pointer to a existing list element, have to be associated to a list.
*
*  \return             Pointer to the next list object or NULL if node was the the last node of list.
*
*  \see LIST_PREV()  LIST_LAST()
*
*  \test Call with an node of a list with only one element. Result must be NULL.
*  \test Call with the last node of a filled list.Result must be NULL.
*  \test Call with the first node of a filled list.Result must be a pointer to the second node.
*  \test Call with any node of a filled list.Result must be a pointer to the next node.
*
*  \hideinitializer
*/
#define LIST_NEXT(node)  ( (node)->next->next ? (node)->next : (void*) 0 )

/** Get previous list element.
*
*  LIST_PREV() will return a pointer to the previous object of the list. If no
*  previous element exist NULL will be returned.
*
*  \param node      Pointer to a list element, have to be associated to a list.
*
*  \return          Pointer to the previous object or NULL if node was the first nod of list.
*
*  \see  LIST_NEXT() LIST_FIRST()
*
*  \test Call with an node of a list with only one element. Result must be NULL.
*  \test Call with the first node of a filled list.Result must be NULL.
*  \test Call with the last node of a filled list.Result must be a pointer to the previous node.
*  \test Call with any node of a filled list.Result must be a pointer to the previous node.
*
*  \hideinitializer
*/
#define LIST_PREV(node)  ( (node)->prev->prev ? (node)->prev : (void*) 0 )

/** Retrieve pointer to first element of list.
*
*  LIST_FIRST() will return the first element of the list. If list is empty NULL will be returned.
*
*  \param list         Handle to an initialized linked list.
*
*  \return             Pointer to the first object in list or
*                       NULL if list is empty.
*
*  \see  LIST_LAST() LIST_NEXT() LIST_PREV() LIST_POP() LIST_UNSHIFT()
*
*  \test Call with a list with only one node result must be NULL.
*  \test Call with the last node of a filled list result must be NULL.
*  \test Call with the any node of a filled list result must right.
*
*  \hideinitializer
*/
#define LIST_FIRST( list )  ( LIST_IS_EMPTY( list ) ?  (void*) 0 : ((list)->header.next ) )

/** Retrieve pointer to last element of list.
*
*  LIST_LAST() will return the last element of the list. If list is empty NULL will be returned.
*
*  \param head      Handle to an existing linked list.
*
*  \return          Pointer to the last object in list or
*                    NULL if list is empty.
*
*  \see  LIST_LAST() LIST_NEXT() LIST_PREV() LIST_POP() LIST_UNSHIFT()
*
*  \test Call with an empty list result must be NULL.
*  \test Call with list with only one node - result must be a pointer to the node.
*  \test Call with filled list - result must be a pointer to the first node.
*
*  \hideinitializer
*/
#define LIST_LAST(head)   ( LIST_IS_EMPTY(head) ? (void*) 0 : ((head)->trailer.prev) )

/** Insert a new element before another.
*
*  LIST_INSERT() will insert a new node before a given node.
*  This node can be at an arbitrary position in the list.
*
*  \param node         Pointer to an object where the new element
*                      will be inserted.\n
*
*  \param gem          Pointer to a new node.
*
*  \see LIST_ATTACH()
*
*  \test Call with the first node of a filled list.
*  \test Call with the last node of a filled list.
*
*  \hideinitializer
*
*/
#define LIST_INSERT( node, gem ) \
do{                              \
   (gem)->prev=(node)->prev;     \
   (gem)->next=node;             \
   (gem)->prev->next=gem;        \
   (node)->prev=gem;             \
}while(0)

/** Insert a new element after another.
*
*  LIST_ATTACH() will insert a new node after a given node.
*  This node can be at an arbitrary position of the list.
*
*  \param node         Pointer to an object where the new element should be
*                       be inserted.
*
*  \param gem          Pointer to a new node.
*
*  \see LIST_INSERT() LIST_UNLINK()
*
*  \hideinitializer
*
*/
#define LIST_ATTACH(node,gem) \
do{                           \
   (gem)->next=(node)->next;  \
   (gem)->prev=node;          \
   (node)->next=gem;          \
   (gem)->next->prev=gem;     \
}while(0)

/** Add element to the start of a list.
*
*  LIST_PUSH_FRONT() will add a new element to the beginning of a
*  list, right before the first element. For an empty list
*  this is equivalent to calling LIST_PUSH_BACK().
*
*  \param list       Handle to an existing linked list.
*
*  \param gem        Pointer to an object associated with
*                     the new list element.
*
*  \see LIST_SHIFT()
*
*  \hideinitializer
*/
#define LIST_PUSH_FRONT(list,gem)                        \
do{                                                      \
   (gem)->next              = (list)->header.next;       \
   (gem)->prev              = (void*)&((list)->header);  \
   (list)->header.next->prev= gem;                       \
   (list)->header.next      = gem;                       \
}while(0)

/** Add element to the end of a list.
*
*  LIST_PUSH_BACK() will add a new element to the end of a list.
*  If you think of the list as a stack, the function pushes
*  a new element on top of the stack.
*
*  \param list         Pointer to the head of a linked list.
*
*  \param gem          Pointer to an object associated with
*                       the new list element.
*
*  \see LIST_POP_FRONT()
*
*  \hideinitializer
*/
#define LIST_PUSH_BACK(list,gem)                      \
do{                                                   \
   (gem)->prev           = (list)->trailer.prev;      \
   (gem)->next           = (void*)&((list)->trailer); \
   (list)->trailer.prev->next = gem;                  \
   (list)->trailer.prev       = gem;                  \
}while(0)

/** Remove element from an arbitrary position of a list.
*
*  LIST_UNLINK() will remove the passed node from a list. If element is not associated with a
*  list the behaviour is undefined.
*
*  \param node         Pointer to the node which will be unlinked.
*
*  \return             Pointer to the object that was associated with
*                       the element removed from the list. If the list
*                       is empty, NULL will be returned.
*
*  \test Call with the node of a list with only one Element. Result should be pointer to this node.
*  \test Call with last node of a filled list. Item is removed from list.
*  \test Call with first node of a filled list. Item is removed from list.
*  \test Call with any node of a filled list.  Item is removed from list.
*
*  \see LIST_UNSHIFT() LIST_POP()
*
*  \hideinitializer
*/
#define LIST_UNLINK(node)              \
do{                                    \
      (node)->prev->next=(node)->next; \
      (node)->next->prev=(node)->prev; \
}while(0)

/** Remove element from the start of a list.
*
*  LIST_POP_FRONT() will remove the first element from a list.
*  If the list contains only a single element, this is
*  equivalent to calling LNL_POP(). If list is empty, NULL will be returned.
*
*  \param list      Handle to an existing linked list.
*
*  \param prt       Pointer to pointer where the object that was associated with
*                    the element removed from the list is stored. If the list
*                    is empty, NULL will be returned.
*
*  \test Call with an empty list. Result should be NULL.
*  \test Call with a list with only one node. Result pointer to this node.
*  \test Call with a filled list. .
*
*  \see LIST_POP_BACK() LIST_UNLINK()
*
*  \hideinitializer
*/
#define LIST_POP_FRONT(list,ptr)    \
do{                                 \
   if( LIST_IS_EMPTY(list))         \
   {                                \
      *(ptr)=(void*) 0;             \
   }                                \
   else                             \
   {                                \
      *(ptr)=(list)->header.next;   \
      LIST_UNLINK( *ptr );          \
   }                                \
}while(0)

/** Remove element from the end of a list.
*
*  LIST_POP_BACK() will remove the last element from a list.
*  If you think of the list as a stack, the function pops
*  an element of the stack.
*
*  \param  list     Handle to an existing linked list.
*  \param  ptr      Pointer to pointer where the object that was associated with
*                   the element removed from the list is stored. If the list
*                   is empty, NULL will be stored.
*
*  \test Call with an empty list. Result should be NULL.
*  \test Call with a list with only one node. Result pointer to this node.
*  \test Call with a filled list. .
*
*  \see LIST_POP_FRONT()
*
*  \hideinitializer
*/
#define LIST_POP_BACK(list,ptr)     \
do{                                 \
   if( LIST_IS_EMPTY(list))         \
   {                                \
      *(ptr)=(void*) 0;             \
   }                                \
   else                             \
   {                                \
      *(ptr)=(list)->trailer.prev;  \
      LIST_UNLINK( *ptr );          \
   }                                \
}while(0)

/** Loop over all list elements.
*
*  \code            LIST_FOR_EACH(p,list)
*                   {
*                      printf("Datapointer is 0x%x",LIST_DATA(p));
*                   }
*  \endcode
*
*  \param p         Variable that will receive a pointer
*                   to the current object.
*
*  \param list      Handle to an existing linked list.
*
*  \test Call with an empty list. Body will never executed.
*  \test Call with a list with only one node. Body executed once.
*  \test Call with a filled list. Body will executed for node in list.
*
*   \hideinitializer
*/
#define LIST_FOR_EACH(list,p)  for( (p)=(list)->header.next; (void*)(p) !=(void*)&((list)->trailer); (p)=(p)->next )

/** Test of emptyness.
*
*  The macro LIST_IS_EMPTY(list) return True if no list element is linked.
*
*  \param list Pointer to a list object.
*
*  \return TRUE if list is empty.
*
*  \hideinitializer
*/
#define LIST_IS_EMPTY( list )    ((void*)((list)->header.next)==(void*)&(list)->trailer)

/** Number of linked nodes.
*
*  Count number of tasklets associated in this list.
*
*  \param list pointer to an existing and initialized list. Its not save to pass NULL.
*  \param pointer to pointer to struct tasklet.
*  \param pointer to an counter variable.
*/
#define LIST_COUNT( list, p, count )   \
do{                                    \
   (*(count))=0;                       \
   LIST_FOR_EACH( list,*(p))           \
   {                                   \
      (*(count))++;                    \
   }                                   \
}while(0)

/*====================================================================================================================*/

#endif

/***********************************************************************************************************************
*                             Copyright 2009 Linde Material Handling. All rights reserved.                             *
***********************************************************************************************************************/
